/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

#define MAX_SIZE (1000)
typedef struct TreeNode* QUEUE_TYPE;

typedef struct queue {
     int head;
     int tail;
     QUEUE_TYPE *num;
 } que; //循环队列

void init_que(que *q) 
{
    q->head = 0;
    q->tail = 0;
    q->num = malloc( sizeof(QUEUE_TYPE) * MAX_SIZE);
}

int is_empty(que *q) {
    return (q->head == q->tail);
}
int is_full(que *q) {
    return ( (q->tail + 1) % MAX_SIZE == q->head);   //牺牲一个空间用于区别判空和判满
}
int que_len(que *q) {
    return ( (q->tail + MAX_SIZE - q->head) % MAX_SIZE );
}
int next_index(int ind) {
    return ((ind + 1) % MAX_SIZE);
}

void add_que(que *q, QUEUE_TYPE val)
{
    if (!is_full(q)) {
        q->num[q->tail] = val;
        q->tail = next_index(q->tail);       
    }
}

QUEUE_TYPE del_que(que *q)
{
    QUEUE_TYPE val;
    if (!is_empty(q)) {
        val = q->num[q->head];
        q->head = next_index(q->head);
        return val;
    } else {
        return NULL;
    }
        
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

//(1)*returnSize:returnSize表示返回数组的个数
//(2)**returnColumnSizes:*returnColumnSizes指向一个数组，其元素对应某一层结点构成一维数组中结点的个数
#define SIZE 1000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int **res, level = 0, node_size = 0;
    if(root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    res = (int **)malloc( sizeof(int *) * SIZE );
    *returnColumnSizes = (int *)malloc(sizeof(int)*SIZE);   //每个数组中的元素个数
    que q; //保存下一次要遍历的节点
    init_que(&q);
    add_que(&q, root);

    while(!is_empty(&q)) {
        node_size = que_len(&q);
        (*returnColumnSizes)[level] = node_size;    //第level层有node_size个节点
        res[level] = malloc( sizeof(int) * node_size);

        int i = 0;
        for (i=0; i<node_size; i++) {   //一次循环处理一个level
            /* 保存当前节点中的val  */
            struct TreeNode *t = del_que(&q);
            res[level][i] = t->val;
            /* 将下一层节点加入队列 */
            if (t->left != NULL) { 
                add_que(&q, t->left);
            }
            if (t->right != NULL) {
                add_que(&q, t->right);
            }
        }
        level++;
    }    

    *returnSize = level;
    return res;
}






